package 代码记录.指定公司代码练习记录.华为_2024.分值200;

import java.util.*;

/**
 * @author zx
 * @create 2024-02-16 14:51
 * 这个代码自己肯定是想不到的；通过debug的方式勉强理解
 */
public class 可以处理的最大任务数_51 {
    /**
     * 这段代码的功能是在给定一些时间区间的情况下，计算出这些区间中不重叠的最大数量。
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] nums = new int[n][2];
        for(int i = 0;i < n;i++) {
            nums[i][0] = sc.nextInt();
            nums[i][1] = sc.nextInt();
        }
        //按照结束时间进行排序-从小到大
        Arrays.sort(nums, Comparator.comparingInt(a -> a[1]));
        //创建一个降序排序的优先队列 priorityQueue，用于存储区间的起始时间
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Comparator.reverseOrder());
        //初始化 pqEnd 为整型最大值，表示当前处理的结束时间。创建计数器 count 用于统计不重叠区间的数量。
        int pqEnd = Integer.MAX_VALUE, count = 0;
        //遍历排序后的数组 nums，对每组起始和结束时间进行处理
        for (int[] num : nums) {
            int start = num[0], end = num[1];
            //如果优先队列非空且结束时间小于 pqEnd 且队列头部元素小于等于 pqEnd，则从队列中取出元素并递增计数器，同时减小 pqEnd。
            while (!priorityQueue.isEmpty() && end < pqEnd && priorityQueue.poll() <= pqEnd) {
                count++;
                pqEnd--;
            }
            //将当前区间的起始时间加入优先队列，更新 pqEnd 为当前区间的结束时间。
            priorityQueue.add(start);
            pqEnd = end;
        }
        //继续处理完所有区间后，再次检查优先队列，此时继续递增计数器和减小 pqEnd 直到队列为空或者队列头部元素大于 pqEnd。
        while (!priorityQueue.isEmpty() && priorityQueue.poll() <= pqEnd) {
            count++;
            pqEnd--;
        }
        //输出最终的计数器值，表示最大数量的不重叠时间区间。
        System.out.println(count);
    }
}
